package algorithms.leaning.class25;

import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

/**
 * 一种特别设计的栈结构，为了解决如下的问题：
 * <p>
 * 给定一个可能含有重复值的数组arr，i位置的数一定存在如下两个信息
 * 1）arr[i]的左侧离i最近并且小于(或者大于)arr[i]的数在哪？
 * 2）arr[i]的右侧离i最近并且小于(或者大于)arr[i]的数在哪？
 * 如果想得到arr中所有位置的两个信息，怎么能让得到信息的过程尽量快。
 * <p>
 * 那么到底怎么设计呢？
 *
 * @author guichang
 * @date 2021/6/27
 */

@SuppressWarnings("all")
public class Code1_单调栈_实现 {

    public static void main(String[] args) {
        MyUtil.printInt(monotonicStack(new int[]{1, 3, 4, 2}));
//        MyUtil.printInt(monotonicStackWithRepeat(new int[]{1, 1, 4, 2, 6}));
    }

    /**
     * 实现一，无重复元素
     *
     * @param array 待处理数组
     * @return [i, 0]-左边离自己最近且最小位置 [i,1]-右边离自己最近且最小位置
     */
    public static int[][] monotonicStack(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        int N = array.length;
        // 答案
        int[][] ans = new int[N][2];
        // 栈从上到下严格从大到小
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            // 如果当前值小于栈顶元素则栈顶要弹出
            while (!stack.isEmpty() && array[i] < array[stack.peek()]) {
                // 记录弹出位置的前后
                Integer top = stack.pop();
                ans[top][1] = i; // 最右最小就是i
                ans[top][0] = stack.isEmpty() ? -1 : stack.peek(); // 最左最小就是下面的一个
            }
            // 当前位置压栈
            stack.push(i);
        }
        // 栈中还有元素依次弹出
        while (!stack.isEmpty()) {
            Integer top = stack.pop();
            ans[top][1] = -1;
            ans[top][0] = stack.isEmpty() ? -1 : stack.peek();
        }
        return ans;
    }

    /**
     * 实现二，有重复元素
     *
     * @param array 待处理数组
     * @return [i, 0]-左边最近最小位置 [i,1]-右边最近最小位置
     */
    public static int[][] monotonicStackWithRepeat(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }
        int N = array.length;
        // 答案
        int[][] ans = new int[N][2];
        Deque<ArrayList<Integer>> stack = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            // 当前值小于栈顶元素
            while (!stack.isEmpty() && array[i] < array[stack.peek().get(0)]) {
                // 记录弹出位置的前后
                ArrayList<Integer> topList = stack.pop();
                // 最后边的数就是i
                int right = i;
                // 最左边的数就是下一个链表的最后一个位置
                int left = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                for (Integer index : topList) {
                    ans[index][1] = right;
                    ans[index][0] = left;
                }
            }
            // 当前位置压栈
            // 此时元素一样或栈空了就要新建一个链表
            if (stack.isEmpty() || array[stack.peek().get(0)] != array[i]) {
                ArrayList<Integer> newList = new ArrayList<>();
                newList.add(i);
                stack.push(newList);
            }
            // 否则就是栈顶元素一样，直接加到链表末尾
            else {
                stack.peek().add(i);
            }
        }
        // 栈中还有元素依次弹出
        while (!stack.isEmpty()) {
            // 记录弹出位置的前后
            ArrayList<Integer> topList = stack.pop();
            // 最左边的数就是下一个链表的最后一个位置
            int left = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            for (Integer index : topList) {
                ans[index][1] = -1; // 右边是-1，因为没值了
                ans[index][0] = left; // 左边是
            }
        }
        return ans;
    }
}